package main

import "fmt"

/**
分析:
	求该数组所有可能的子集等同于求每个位置的值构成的集合加包含该值的全部子集的总和

	回溯法
	比如输入1,2,3
	[]=>[1]=>[1 2] => [1 2 3]
		   =>[1 3]
	  =>[2]=>[2 3]
      =>[3]
*/

func main() {
	nums := []int{1, 2, 3}
	res := subsets(nums)
	fmt.Println(res)
}

func subsets(nums []int) [][]int {
	if len(nums) == 0 {
		return [][]int{}
	}

	res, list, index := [][]int{}, []int{}, 0
	subsetsHelper(&res, nums, list, index)
	return res
}

func subsetsHelper(res *[][]int, nums []int, list []int, index int) {
	//将当前位置构成的数组加入符合条件的情况res中
	tmp := make([]int, len(list))
	copy(tmp, list)
	*res = append(*res, list)

	for i := index; i < len(nums); i++ {
		list = append(list, nums[i])
		subsetsHelper(res, nums, list, i+1)
		list = list[:len(list)-1]
	}
}
